package LC;

import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/
 * Given a binary tree
 * struct TreeLinkNode {
 * TreeLinkNode *left;
 * TreeLinkNode *right;
 * TreeLinkNode *next;
 * }
 * Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
 * Initially, all next pointers are set to NULL.
 * Note:
 * You may only use constant extra space.
 * You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
 * For example,
 * Given the following perfect binary tree,
 * 1
 * /  \
 * 2    3
 * / \  / \
 * 4  5  6  7
 * After calling your function, the tree should look like:
 * 1 -> NULL
 * /  \
 * 2 -> 3 -> NULL
 * / \  / \
 * 4->5->6->7 -> NULL
 */
public class LC_116_PopulatingNextRightPointersinEachNode_LinkedBinaryTree {

    public static void main(String[] args) {

    }

    static class TreeLinkNode {
        int val;
        TreeLinkNode left, right, next;

        TreeLinkNode(int x) {
            val = x;
        }
    }

    static class Solution {
        static void connect(TreeLinkNode root) {
            if (root == null) return;
            if (root.left == null && root.right == null) root.next = null;

            List<TreeLinkNode> list = new LinkedList<>();
            list.add(root);
            int count = 0;
            int level = 0;
            int levelCount = 1;
            while (list.size() != 0) {
                TreeLinkNode fis = list.remove(0);
                count++;
                if (list.size() >= 0 && count != levelCount) {
                    fis.next = list.get(0);
                } else {
                    fis.next = null;
                    level++;
                    levelCount = (int) Math.pow(2, level);
                    count = 0;
                }
                if (fis.left != null) list.add(fis.left);
                if (fis.right != null) list.add(fis.right);
            }
        }
    }
}